package com.example.zzy.zzytest.algo.sort.nlognsort;

import java.util.Arrays;

/**
 * 归并排序
 * 归：找中间值，分成左右两个数组，然后往左往右递归找中间值，分数组，分成最细就是数组只有1个元素
 * 并：把左右两个有序数组合起来，创建一个temp数组，把左右往里放，最后把剩余的一股脑放进去
 */
public class MergeSort {
    public static int[] mergeSort(int[] srcArray) {
        if (srcArray.length <= 1) {
            return srcArray;
        }
        int[] arr = Arrays.copyOf(srcArray, srcArray.length);
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        int[] leftSorted = mergeSort(left);
        int[] rightSorted = mergeSort(right);

        return merge(leftSorted, rightSorted);
    }

    public static int[] merge(int[] left, int[] right) {
        int[] temp = new int[left.length + right.length];
        int i = 0, j = 0, index = 0;
        while (true) {
            if (i == left.length || j == right.length) {
                break;
            }
            if (left[i] <= right[j]) {
                temp[index++] = left[i++];
            } else {
                temp[index++] = right[j++];
            }
        }

        if (i < left.length) {
            while (index < temp.length) {
                temp[index++] = left[i++];
            }
        }

        if (j < right.length) {
            while (index < temp.length) {
                temp[index++] = right[j++];
            }
        }

        return temp;
    }

    /**
     *
     */
    public static void main(String[] args) {
        //测试排序
//        int[] testArr = new int[]{-9, 78, 0, 23, -567, 70, 3};
//        int[] result = mergeSort(testArr);
//        for (int i : result) {
//            System.out.print(i + " ");
//        }

        //利用归并排序求数组小和 nlogn
        //1,3,4,2,5 比1大的4个，比3大的2个，比4大的1个，比2大的1个 4+6+4+2=16
        int[] nums = new int[]{1,3,4,2,5};
        System.out.println(smallSum(nums, 0, 4));
    }

    public static int smallSum(int[] arr, int l, int r) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        if (l == r) {
            return 0;
        }
        int m = l + ((r - l) >> 1);
        return smallSum(arr, l, m) + smallSum(arr, m + 1, r) + merge1(arr, l, m, r);
    }


    private static int merge1(int[] arr, int l, int m, int r) {
        //额外数组和他的index
        int i = 0;
        int[] temp = new int[r - l + 1];
        //归并时的左右指针
        int left = l;
        int right = m + 1;
        //小和
        int res = 0;
        while (left <= m && right <= r) {
            //左边的数字小，才会产生小和
            res += arr[left] < arr[right] ? arr[left] * (r - right + 1) : 0;
            //往额外数组拷贝时，遇到左右相等的情况，必须先复制右边数组的数字
            temp[i++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
        }
        while (left<=m){
            temp[i++] = arr[left++];
        }
        while (right<=r){
            temp[i++] = arr[right++];
        }
        for(i = 0; i<temp.length; i++){
            arr[l+i] = temp[i];
        }

        return res;
    }

}
